package day190720;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/7/20 下午 09:39
 * 12. 整数转罗马数字
 * https://leetcode-cn.com/problems/integer-to-roman/
 */
public class IntToRoman {
    public String intToRoman(int num) {
        StringBuilder result = new StringBuilder();
        while (num >= 1000) {
            result.append("M");
            num -= 1000;
        }
        if (num >= 900) {
            result.append("CM");
            num -= 900;
        }
        while (num >= 500) {
            result.append("D");
            num -= 500;
        }
        if (num >= 400) {
            result.append("CD");
            num -= 400;
        }
        while (num >= 100) {
            result.append("C");
            num -= 100;
        }
        if (num >= 90) {
            result.append("XC");
            num -= 90;
        }
        while (num >= 50) {
            result.append("L");
            num -= 50;
        }
        if (num >= 40) {
            result.append("XL");
            num -= 40;
        }
        while (num >= 10) {
            result.append("X");
            num -= 10;
        }
        if (num >= 9) {
            result.append("IX");
            num -= 9;
        }
        while (num >= 5) {
            result.append("V");
            num -= 5;
        }
        if (num >= 4) {
            result.append("IV");
            num -= 4;
        }
        while (num >= 1) {
            result.append("I");
            num -= 1;
        }
        return result.toString();
    }


    public int numEquivDominoPairs(int[][] dominoes) {
        int result = 0;
        int[][] sum = new int[10][10];
        for (int i = 0; i < dominoes.length; i++) {
            int a = dominoes[i][0];
            int b = dominoes[i][1];
            sum[a][b] ++;
            sum[b][a] ++;
//            for (int j = i + 1; j < dominoes.length; j++) {
//                int c = dominoes[j][0];
//                int d = dominoes[j][1];
//                if ((a == c && b == d) || (a == d && b == c)) {
//                    result ++;
//                }
//            }
        }
//        for (int i = 0; i < dominoes.length; i++) {
//            sum[dominoes[i][0] + dominoes[i][1]] ++;
//        }
        for (int i = 0; i < sum.length; i++) {
            for (int j = 0; j <= 5; j++) {
                if (sum[i][j] == 0) {
                    continue;
                }
                result += function(sum[i][j]);
            }
        }
        return result;
    }

    private int function(int n) {
        if (n == 0 || n == 1)
            return 0;
        if (n == 2) {
            return 1;
        }
        return function(n - 1) + function(n - 2);
    }


    public int mctFromLeafValues(int[] arr) {
        return 0;
    }
}
